package com.ruoyi.learn.java.algorithm.sort;

public class InsertionSort {
    // 插入排序方法
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        // 从第二个元素开始，因为第一个元素默认已排序
        for (int i = 1; i < n; i++) {
            int key = arr[i];  // 当前要插入的元素
            int j = i - 1;     // 已排序部分的最后一个元素索引

            // 将大于key的元素向后移动一位
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 将key插入到正确位置
            arr[j + 1] = key;
        }
    }

    // 打印数组的方法
    public static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // 主方法，用于测试
    public static void main(String[] args) {
        int[] testArray = {12, 11, 13, 5, 6};
        System.out.println("排序前的数组:");
        printArray(testArray);

        // 调用插入排序
        insertionSort(testArray);

        System.out.println("排序后的数组:");
        printArray(testArray);
    }
}
